Computers, such as PCs, workstations, servers, routers, cell phones, and PDAs possibly receive attacks from the outside of the computers or the inside of the computers. Typical attacks include an attack which exploits the vulnerabilities of software executed on a computer. Attackers send a code for exploiting the vulnerabilities of software to a computer, thereby taking control of processes included in the software executed on the computer. The attackers utilize the authority of the processes under their control to perform invalid operation.
Against this background, there has been known an anomaly detection system which detects an attack exploiting the vulnerabilities of software, in particular, an attack unknown to the computer.
Specifically, in the anomaly detection system, a model of the normal behavior of software is formed in advance and the behavior model thus formed is stored. During execution of the software, the anomaly detection system determines if the behavior of the software is different from the behavior model.
The attackers use a system call in which a process requests a kernel to perform important processing so as to cause a computer to operate an intended operation. Accordingly, it is important to verify the validity of a system call in monitoring the behavior of software.
In response to this, there has been proposed a verification method for verifying the validity of a system call during execution of software. However, it has been found that an attack can be made while a system call sequence is kept normal. Thus, in order to improve verification accuracy, there has been proposed a method which uses not only a system call but also a return address for verification. This verification method utilizes the status of a call stack in which return addresses and the like are stored. Specifically, this verification method includes stages of training the behavior of software and verifying the behavior of the software (for example, Non-patent literature 1).
At the stage of training the behavior of software, the software is normally executed in advance to generate a behavior model of the software.
Specifically, when a system call occurs, the status of the call stack (the sequence of return addresses stored in the call stack) is acquired and simultaneously a value of a program counter is acquired. A virtual stack list is generated, that the sequence of the return addresses and the value of the program counter are recorded. Subsequently, acquired is difference information (virtual path) between the virtual stack list generated when one system call occurs and the virtual stack list generated when another system call occurs following the one system call. Furthermore, a hash table is generated based on the virtual stack list and the difference information (virtual path). The hash table is utilized as a behavior model.
At the stage of verifying the behavior of the software, when a system call occurs during execution of the software, a hash table is generated in the same manner as in the stage of training the behavior of the software. Subsequently, matching is performed between the hash table generated at the stage of training the behavior of the software and the hash table generated during execution of the software. The system call is authorized when the hash tables coincide with each other, whereas it is determined that the behavior of the software is abnormal when the hash tables do not coincide with each other.
However, in the above-described verification method, a hash table has to be generated based on the virtual stack list and the difference information (virtual path). In particular, at the stage of verifying the behavior of software, a hash table has to be generated during execution of the software. Thus, a processing load on a computer becomes heavy, which results in slowing down the processing speed of the computer. In particular, it should be noted that a load of generating difference information (virtual path) for acquiring the hash table is heavy.
In addition, in Non-patent literature 1, behaviors already trained are regarded as normal and behaviors not trained yet are all regarded as abnormal. In other words, if not all the behaviors are trained, error detection possibly occurs in which even a normal behavior is determined as abnormal. To comprehensively train the normal behaviors of software is difficult in practice. Accordingly, this is considered as a problem.    Non-patent literature 1: H. Feng et al., “Anomaly Detection Using Call Stack Information,” The proc. of IEEE Symposium on Security and Privacy 2003, pp. 62.